package com.wlj.utils.suanfa;

/**
 * 377
 * 给定一个整数数组，没有重复元素。问有多少种可能，使用这数组中的数字凑出一个指定的整数target
 * 如: nums[1,2,3]，target=4
 * 可能的组合: [1,1,1,1] [1,1,2] [1,2,1] [2,1,1] [1,3] [3,1] [2,2]
 * 共有7种
 * 注意:顺序性
 *
 * F(n,c) :考虑使用[0..n]范围里的数字凑出c -> 状态定义
 * 状态转移方程:     F(n,c)=F(n,c-nums[0])+F(n,c-nums[1])+F(n,c-nums[2])...F(n,c-nums[n])   每个F(n,c)的前提条件:nums[i]<=当前容量
 */
public class Suanfa06 {


    public static int clumb_sum(int nums[],int target){

        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int[] dp = new int[target + 1];

        // 注意：理解这一句代码的含义
        dp[0] = 1;

        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < len; j++) {
                if (i >=nums[j]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }


    public static void main(String[] args) {
        int nums[]={1,2,3};
        System.out.println(clumb_sum(nums,4));
    }
}
